The AQ Methods for Concept Drift.

Detecting Insider Theft of Trade Secrets.

Paired Learners for Concept Drift.

elicit A System for Detecting Insiders Who Violate Need%2Dto%2DKnow.

Learning to Detect and Classify Malicious Executables in the Wild.
We describe the use of machine learning and data mining to detect and classify malicious executables as they appear in the wild. We gathered 1,971 benign and 1,651 malicious executables and encoded each as a training example using n-grams of byte codes as features. Such processing resulted in more than 255 million distinct n-grams. After selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive Bayes, decision trees, support vector machines, and boosting. Ultimately, boosted decision trees outperformed other methods with an area under the ROC curve of 0.996. Results suggest that our methodology will scale to larger collections of executables. We also evaluated how well the methods classified executables based on the function of their payload, such as opening a backdoor and mass-mailing. Areas under the ROC curve for detecting payload function were in the neighborhood of 0.9, which were smaller than those for the detection task. However, we attribute this drop in performance to fewer training examples and to the challenge of obtaining properly labeled examples, rather than to a failing of the methodology or to some inherent difficulty of the classification task. Finally, we applied detectors to 291 malicious executables discovered after we gathered our original collection, and boosted decision trees achieved a true-positive rate of 0.98 for a desired false-positive rate of 0.05. This result is particularly important, for it suggests that our methodology could be used as the basis for an operational system for detecting previously undiscovered malicious executables.
Using additive expert ensembles to cope with concept drift.
We consider online learning where the target concept can change over time. Previous work on expert prediction algorithms has bounded the worst-case performance on any subsequence of the training data relative to the performance of the best expert. However, because these “experts ” may be difficult to implement, we take a more general approach and bound performance relative to the actual performance of any online learner on this single subsequence. We present the additive expert ensemble algorithm AddExp, a new, general method for using any online learner for drifting concepts. We adapt techniques for analyzing expert prediction algorithms to prove mistake and loss bounds for a discrete and a continuous version of AddExp. Finally, we present pruning methods and empirical results for data sets with concept drift. 1.
Learning to detect malicious executables in the wild.
We describe the use of machine learning and data mining to detect and classify malicious executables as they appear in the wild. We gathered 1,971 benign and 1,651 malicious executables and encoded each as a training example using n-grams of byte codes as features. Such processing resulted in more than 255 million distinct n-grams. After selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive Bayes, decision trees, support vector machines, and boosting. Ultimately, boosted decision trees outperformed other methods with an area under the ROC curve of 0.996. Results suggest that our methodology will scale to larger collections of executables. We also evaluated how well the methods classified executables based on the function of their payload, such as opening a backdoor and mass-mailing. Areas under the ROC curve for detecting payload function were in the neighborhood of 0.9, which were smaller than those for the detection task. However, we attribute this drop in performance to fewer training examples and to the challenge of obtaining properly labeled examples, rather than to a failing of the methodology or to some inherent difficulty of the classification task. Finally, we applied detectors to 291 malicious executables discovered after we gathered our original collection, and boosted decision trees achieved a true-positive rate of 0.98 for a desired false-positive rate of 0.05. This result is particularly important, for it suggests that our methodology could be used as the basis for an operational system for detecting previously undiscovered malicious executables.
Incremental learning with partial instance memory.
Learning concepts that change over time is important for a variety of applications in which an intelligent system must acquire and use a behavioral profile. Computer intrusion detection, calendar scheduling, and intelligent user interfaces are three examples. An interesting class of methods for learning such concepts consists of algorithms that maintain a portion of previously encountered examples. Since concepts change over time and these methods store selected examples, mechanisms must exist to identify and remove irrelevant examples of old concepts. In this paper, we describe an incremental rule learner with partial instance memory, called AQ11-PM+WAH, that uses Widmer and Kubat&#039;s heuristic to adjust dynamically the window over which it retains and forgets examples. We evaluated this learner using the STAGGER Concepts and made direct comparisons to AQ-PM and to AQ11-PM, similar learners with partial instance memory. Results suggest that the forgetting heuristic is not restricted to FLORA2, the learner for which it was originally designed. Overall, results from this study and others suggest learners with partial instance memory converge more quickly to changing target concepts than algorithms that learn solely from new examples.
Dynamic Weighted Majority A New Ensemble Method for Tracking Concept Drift.
Algorithms for tracking concept drift are important for many applications. We present a general method based on the Weighted Majority algorithm for using any on-line learner for concept drift. Dynamic Weighted Majority (DWM) maintains an ensemble of base learners, predicts using a weighted-majority vote of these &#034;experts&#034;, and dynamically creates and deletes experts in response to changes in performance. We empirically evaluated two experimental systems based on the method using incremental naive Bayes and Incremental Tree Inducer (ITI) as experts.
A General Model for Finite%2DSample Effects in Training and Testing of Competing Classifiers.
The conventional wisdom in the field of statistical pattern recognition (SPR) is that the size of the finite test sample dominates the variance in the assessment of the performance of a classical or neural classifier. The present work shows that this result has only narrow applicability. In particular, when competing algorithms are being compared, the finite training sample more commonly dominates this uncertainty. This general problem in SPR is analyzed using a formal structure recently developed for multivariate random-effects receiver operating characteristic (ROC) analysis. Monte Carlo trials within the general model are used to explore the detailed statistical structure of several representative problems in the sub-field of computeraided diagnosis in medicine. The scaling laws between variance of accuracy measures and number of training samples and number of test samples are investigated and found to be comparable to those discussed in the classic text of Fukunaga, but important interaction terms have been neglected by previous authors. Finally, the importance of the contribution of finite trainers to the uncertainties argues for some form of bootstrap analysis to sample that uncertainty. The leading contemporary candidate is an extension of the 0.632 bootstrap and associated error analysis, as opposed to the more commonly used cross-validation.
Improved Rooftop Detection in Aerial Images with Machine Learning.
In this paper, we examine the use of machine learning to improve a rooftop detection process, one step in a vision system that recognizes buildings in overhead imagery. We review the problem of analyzing aerial images and describe an existing system that detects buildings in such images. We briefly detail four algorithms that we selected to improve rooftop detection. The data sets were highly skewed and the cost of mistakes differed between the classes, so we used ROC analysis to evaluate the methods under varying error costs. We report three experiments designed to illuminate facets of applying machine learning to the image analysis task. One investigated learning with all available images to determine the best performing method. Another focused on within-image learning, in which we derived training and testing data from the same image. A final experiment addressed between-image learning, in which training and testing sets came from different images. Results suggest that useful generalization occurred when training and testing on data derived from images differing in location and in aspect. They demonstrate that under most conditions, naive Bayes exceeded the accuracy of other methods and a handcrafted classifier, the solution currently used in the building detection system.
On Machine Learning%2C ROC Analysis%2C and Statistical Tests of Significance.
ROC analysis is being used with greater frequency as an evaluation methodology in machine learning and pattern recognition. Researchers have used ANOVA to determine if the results from such analysis are statistically significant. Yet, in the medical decision making community, the prevailing method is LABMRMC. Although this latter method uses ANOVA, before doing so, it applies the Jackknife method to account for case-sample variance. To determine whether these two tests make the same decisions regarding statistical significance, we conducted a Monte Carlo simulation using several problems derived from Gaussian distributions, three machine-learning algorithms, ROC analysis, ANOVA, and LABMRMC. Results suggest that the decisions these tests make are not the same, even for simple problems. Furthermore, the larger issue is that since ANOVA does not account for case-sample variance, one cannot generalize experimental results to the population from which the data were drawn.
Incremental Learning with Partial Instance Memory.
Learning concepts that change over time is important for a variety of applications in which an intelligent system must acquire and use a behavioral profile. Computer intrusion detection, calendar scheduling, and intelligent user interfaces are three examples. An interesting class of methods for learning such concepts consists of algorithms that maintain a portion of previously encountered examples. Since concepts change over time and these methods store selected examples, mechanisms must exist to identify and remove irrelevant examples of old concepts. In this paper, we describe an incremental rule learner with partial instance memory, called AQ11-PM+WAH, that uses Widmer and Kubat&#039;s heuristic to adjust dynamically the window over which it retains and forgets examples. We evaluated this learner using the STAGGER Concepts and made direct comparisons to AQ-PM and to AQ11-PM, similar learners with partial instance memory. Results suggest that the forgetting heuristic is not restricted to FLORA2, the learner for which it was originally designed. Overall, results from this study and others suggest learners with partial instance memory converge more quickly to changing target concepts than algorithms that learn solely from new examples.
An Initial Study of an Adaptive Hierarchical Vision System.
We describe an empirical study of an adaptive,  hierarchical vision system. Using a simple  vision task requiring both low-level and  high-level processing, we examined how three  schemes of feedback for on-line learning affected  the true positive rate, the number of  instances used for learning, and the need for  user feedback. The rst scheme used for  learning those instances for which the user  provided feedback. The second used all instances,  assuming that no feedback meant  correct classication. In the end, a hybrid  scheme with each method at dierent levels  yielded the best results, showing that more  examples for learning signicantly improved  the true positive rate of the classiers at  the lower level, but not at the higher level.  Furthermore, this hybrid method did not increase  the need for user feedback.  1. Introduction  Hierarchical vision systems (Mohan &amp; Nevatia, 1989) work by repeatedly grouping visual constructs into higher-level constructs and selecting the m...
Selecting Examples for Partial Memory Learning.
. This paper describes a method for selecting training examples for a partial memory learning system. The method selects extreme examples that lie at the boundaries of concept descriptions and uses these examples with new training examples to induce new concept descriptions. Forgetting mechanisms also may be active to remove examples from partial memory that are irrelevant or outdated for the learning task. Using an implementation of the method, we conducted a lesion study and a direct comparison to examine the effects of partial memory learning on predictive accuracy and on the number of training examples maintained during learning. These experiments involved the STAGGER Concepts, a synthetic problem, and two real-world problems: a blasting cap detection problem and a computer intrusion detection problem. Experimental results suggest that the partial memory learner notably reduced memory requirements at the slight expense of predictive accuracy, and tracked concept drift as well as ot...
Modifying Rete to Reason Temporally.

